\documentclass[xcolor=dvipsnames]{beamer}

\usepackage[greek,french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[LGR,T1]{fontenc}
\usepackage{lmodern}
\usepackage{graphicx}



\usepackage[hang]{caption}
%\usepackage{multirow}



\usepackage{beamerOral} % contient toutes la mise en forme Beamer




%--------------- Informations ---------------------------------------------

\title{Data mining using SWARM}
\author[WINDELS\and SCHWARZ\and SPUDVILAS\and PILVINYTE\and BAALI]{Gaetan WINDELS\and Ivan SCHWARZ\and Julius SPUDVILAS\and Aiste PILVINYTE\and Etienne BAALI}
\institute{Aalborg University}
\date{\today}
\misc{Semester project DE7}

%--------------------- Début du document ----------------------------
\begin{document}

\begin{frame}
\titlepage
\end{frame}


\begin{frame}\frametitle{Plan}
\tableofcontents[hideallsubsections]
\end{frame}


%\section*{Introduction}
\begin{frame}\frametitle{Introduction}
	\begin{block}{Introduction}
	
		\begin{itemize}

			\item Trajectory mining
			\item Blah blah
			\item blah Blah blah

		\end{itemize}

	\end{block}


	\begin{block}{Objectives}

		\begin{itemize}

			\item Blah blah
			\item blah Blah blah
			\item Blah blah
			\item blah Blah blah

		\end{itemize}		
	
	\end{block}

\end{frame}

\begin{frame}\frametitle{OR}
	OR
\end{frame}

\begin{frame}\frametitle{Introduction}
	\begin{itemize}
		\item Introduction
		\item Objectives
	\end{itemize}
\end{frame}


\section{Clustering}

\begin{frame}\frametitle{Example of picture + text}
	\begin{columns}
		\begin{column}{0.4\textwidth}

			\begin{block}{Comment on the picture}
				\begin{itemize}
					\item On the top not merged, blah blah
					\item On the bottom merged, blah blah
				\end{itemize}
			\end{block}
		
		\end{column}
		\begin{column}{0.6\textwidth}
			\begin{figure}
				\includegraphics[width=1\textwidth]{images/appPeriodic.png}
				\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Periodically merge trajectories}}
			\end{figure}

		\end{column}
	\end{columns}
\end{frame}




\begin{frame}\frametitle{Related work}
	\begin{block}{Different clustering methods}
	
		\begin{itemize}

			\item K-means
			\item Hyerarchical

		\end{itemize}

	\end{block}
	
	\begin{block}{Cons \& Pros}
	
		\begin{itemize}

			\item Good for this
			\item Bad for that
			\item Blah

		\end{itemize}

	\end{block}

\end{frame} 

\subsection{DBSCAN}

\begin{frame}\frametitle{DBSCAN}
	BLAH
		%\begin{figure}
		%		\includegraphics[width=0.6\textwidth]{images/schemaReseau.png}
		%		\renewcommand{\figurename}{{\tiny Graphique }}\caption{{\tiny Schéma d'un réseau de capteurs}}
		%\end{figure}
\end{frame}


\section{Moving patterns}

\begin{frame}\frametitle{Related work}
	
	\begin{figure}
		\includegraphics[width=0.7\textwidth]{images/moving_pattern_paper.png}
		\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Loss of interesting objects with Simple patterns, Flocks, Convoys}}
	\end{figure}
	
	\begin{block}{Moving patterns}
		\begin{itemize}
			\item Simple patterns, Flocks, Convoys - objects have to be together for any two consecutive timestamps
			\item Swarms - at least $min_{o}$ objects which are together at least $min_{t}$ timestamps
		\end{itemize}
	\end{block}
\end{frame}

\subsection{Investigating single swarm}

\begin{frame}\frametitle{Investigating single swarm}
	
	\begin{figure}
		\includegraphics[width=0.9\textwidth]{images/SwarmsBig.png}
		\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Single swarm with 5 objects}}
	\end{figure}
	
\end{frame}

\begin{frame}\frametitle{Investigating single swarm}
	
	\begin{figure}
		\includegraphics[width=0.9\textwidth]{images/SwarmsBig2.png}
		\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Possible behavior of these objects between $t_{3}$ and $t_{8}$.}}
	\end{figure}
	
\end{frame}

\subsection{Horde concept}

\begin{frame}\frametitle{Horde concept}

	\begin{block}{Introduction}
	
		\begin{itemize}
			\item Based on swarms
			\item Stronger relation between moving objects
		\end{itemize}
	
	\end{block}
	
	\begin{block}{Definition}
	
		\begin{itemize}
			\item Set of moving objects
			\item In the same swarm for at least $min_{s}$ swarms
			\item Closed horde
		\end{itemize}
	
	\end{block}
	
	\begin{block}{Application}
		
		\begin{itemize}
			\item Friend recommendation
			\item Carpool propositions
		\end{itemize}
		 
	\end{block}
	
\end{frame}

\subsection{Periodic patterns}

\begin{frame}\frametitle{Periodic patterns}
	\begin{block}{Period finder swarm}
	
		\begin{itemize}
			\item Obtained by merging the time
			\item \textit{Contain the same user several times}
			\item \textit{Swarm still catches it if detour}
		\end{itemize}
	
	\end{block}	

	\begin{block}{Application}
	
		\begin{itemize}
			\item Periodic behaviour detection
			\item \textit{Traffic jams}
		\end{itemize}
	
	\end{block}	
\end{frame}


\section{Implementation and experiments}
	
\subsection{Dataset}
	
\begin{frame}\frametitle{Dataset}
	
	\begin{columns}
		\begin{column}{0.6\textwidth}
			\begin{itemize}
				\item Public dataset from Beijing GPS users
				\item 167 different users from 2007 to 2011
			\end{itemize}
			
			\begin{block}{Big dataset}
		Need to preprocess this hudge amount of data :
		\begin{itemize}
			\item To repair user errors
			\item To get dense enough data
		\end{itemize}
	\end{block}
		\end{column}
		\begin{column}{0.4\textwidth}
			\begin{figure}
				\includegraphics[width=1\textwidth]{images/vue_beijing.png}
				\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Data overview in Beijing}}
			\end{figure}

		\end{column}
	\end{columns}
	
\end{frame}


\subsection{Pre-processing}
	
\begin{frame}\frametitle{Pre-processing to repair user errors}
	More than one trajectory in one file.

	\begin{columns}
		
		\begin{column}{0.6\textwidth}
			\begin{figure}
				\includegraphics[width=0.9\textwidth]{images/DB.png}
				\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Data structure}}
			\end{figure}
		\end{column}
		
		\begin{column}{0.4\textwidth}
			
			\begin{block}{Processing}
				Implementation choice, when there is more than one trajectory in a file \fleche split it in 2 files !				
			\end{block}
		\end{column}
	\end{columns}
	\begin{block}{}
		Then we get a structure suitable for the interpolation pre-processing.
	\end{block}
	
\end{frame}

\begin{frame}\frametitle{Pre-processing to get dense enough data}
	
	Fill the gaps that can happen to get data closer to the actual behavior of the user.
	\newline
	Two reasons : 
	\begin{itemize}
		\item Signal lost
		\item Speed too high
	\end{itemize}
	\begin{figure}
		\includegraphics[width=0.7\textwidth]{images/interpolation.png}
		\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Linear interpolation}}
	\end{figure}
	 
	
\end{frame}

\subsection{Processing}
	%maybe for the DBSCAN subsection
\begin{frame}\frametitle{Make the clusters}
	Usage of DBSCAN to form the clusters.\newline
	\begin{columns}[t]
		\begin{column}{0.6\textwidth}
			Global usage :
			\begin{figure}
				\includegraphics[width=1.1\textwidth]{images/DBSCAN_solution.png}
				\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny DBSCAN usage}}
			\end{figure}
		\end{column}
		
		\begin{column}{0.4\textwidth}
			Distance calculation :			
			\begin{figure}
				\includegraphics[width=0.7\textwidth]{images/Distance_perspective.png}
				\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Distance calculation}}
			\end{figure}
		\end{column}
	\end{columns}
	
\end{frame}

\begin{frame}\frametitle{DBSCAN}
	\begin{block}{Input}
		Database : $\forall i \in [0,nbUsers[ \;\; user_{i}$ \fleche files
	\end{block}
	Calculate symilarity on the fly (memory limitation).\\
	Adapt the algorithm to suit to swarm needs.
	\begin{block}{Output}
		Write clusters in a file in a specific format.\\
		Each cluster is of the form : \\		
		\{\\
		<cluster timestamp>\\
		<latitude> < longitude> <user> (for each point in the cluster) \\
		...\\
		<latitude> < longitude> <user> \\
		\}
	\end{block}

\end{frame}

\begin{frame}\frametitle{Finding swarms}
	
	
	\begin{figure}[t]
		\includegraphics[width=0.8\textwidth]{images/BTreeImpl.png}
		\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny B-Tree creation}}
	\end{figure}			
	\begin{block}{}
		{\centering Complexity to create the B-Tree is $2^{|Odb|} x 2^{|Tdb|}$. \\
		Where Odb, is object database and Tdb is timestamp database.}
	\end{block}

\end{frame}

\begin{frame}\frametitle{Pruning rules}

	\begin{block}{Apriori Pruning}
	If for an object set O, the number of timestamp they are together is smaller than the input parameter $min_{t}$, we know that no superset of this O can be found as a closed swarm.
	\end{block}
	
	\begin{block}{Backward Pruning}
	Because we are only looking for closed swarms and because the B-Tree creation algorithm is DFS, we can apply backward pruning.\\
	When we create an object set O' by adding a new object $o_{i}$ to O without reducing the timestamp set, we know that for any other object set containing the object from O without $o_{i}$, we will not reach a closed swarm.
	\end{block}
\end{frame}
		
\begin{frame}\frametitle{Pruning rules}	

	\begin{figure}[t]
		\includegraphics[width=1\textwidth]{images/BTree_paper.png}
		\renewcommand{\figurename}{{\tiny Figure }}\caption{{\tiny Partial B-Tree from paper "Swarm - Mining Relaxed Temporal Moving Object Clusters"}}
	\end{figure}
	\begin{block}{$min_{o}$ = 2 ; $min_{t}$ = 2}
		\begin{itemize}
			\item Apriori pruning rule.
			\item Backward pruning rule.
		\end{itemize}
	\end{block}
\end{frame}	
%\section*{Conclusion}

\begin{frame}\frametitle{Conclusion}
	\begin{itemize}
		\item Conclusion
		\item Futher research
	\end{itemize}
\end{frame}


\begin{frame}\frametitle{Conclusion}
	
\end{frame}



\begin{frame}\frametitle{Further research}
	
\end{frame}


\end{document}
